﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Porownywarka.Interfejsy;

namespace Porownywarka.Sortowanie
{
    public class HeapSort<T> :  ISortMethod<T>
        where T : IComparable<T>
    {

        public T[] SortedData { get; private set; }

        public T[] Sort(T[] tablica, object l)
        {
            T[] tab2;

            lock(l)
            {
                tab2 = (T[])tablica.Clone();    
            }
            
            SortedData = tab2;

            return Sort(ref tab2);
        }

        private T[] Sort(ref T[] tab)
        {
            int count = tab.Length;
            Kopcuj(ref tab);

            int end = count - 1;

            while (end > 0)
            {
                T temp = tab[end];
                tab[end] = tab[0];
                tab[0] = temp;

                end--;

                ShiftDown(ref tab, 0, end);
            }

            return tab;
        }

        private void Kopcuj(ref T[] tab)
        {
            int start = (tab.Length - 2)/2;

            while (start >= 0)
            {
                ShiftDown(ref tab, start, tab.Length -1);
                start--;
            }
        }

        private void ShiftDown(ref T[] tab, int root, int end)
        {
            while( root * 2 + 1 <= end )
            {
                int child = root*2 + 1;
                int swap = root;

                if (tab[swap].CompareTo(tab[child]) < 0)
                    swap = child;

                if (child + 1 <= end && tab[swap].CompareTo(tab[child + 1]) < 0)
                    swap = child + 1;

                if(swap != root)
                {
                    T temp = tab[root];
                    tab[root] = tab[swap];
                    tab[swap] = temp;

                    root = swap;
                }
                else
                    break;
            }
        }
    }
}
